// 任务1
// 这里就是用的BF，找到匹配项，然后输出结果
void
task1(const Row *rows, int nrows)
{
	int i;
    
    for (i = 0;i < nrows;i++)
    {
        if ((1000 == rows->a || 2000 == rows->a || 3000 == rows->a) && (rows->b >= 10 && rows->b < 50))
        {
            printf("%d,%d\n", rows->a, rows->b);
        }
        
        rows++;
    }
    
    return ;
}

// 任务2
/* 思路是使用二分法找到a分别为1000， 2000， 3000的首尾row
 * 然后在每对首尾之间对b寻找20->50的首尾
 * 寻找时间为O(log(N)), 输出时间为O(log(N))->O(N),空间复杂度O(1)
 * */
///@brief 返回首个target的位置，如果存在
int aBinarySearchStart(const Row *rows, int left, int right, int target)
{
    int mid = -1;
    
    while (left < right)
    {
        mid = (left + right) / 2;
        
        if (rows[mid].a >= target)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    
    return left; 
}

///@brief 返回末尾target的位置，如果存在
int aBinarySearchEnd(const Row *rows, int left, int right, int target)
{
    int mid = -1;
    
    while (left < right)
    {
        mid = (left + right) / 2;
        
        if (rows[mid].a > target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    
    return right; 
}

///@brief 返回首个target的位置，如果存在
int bBinarySearchStart(const Row *rows, int left, int right, int target)
{
    int mid = -1;
    
    while (left < right)
    {
        mid = (left + right) / 2;
        
        if (rows[mid].b >= target)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    
    return rows[left].b >= target?left:left+1; 
}

void
task2(const Row *rows, int nrows)
{
    int i, j, target, aStart, aEnd, bStart, bEnd;
    
    for (i = 1;i < 4;i++)
    {
        target = i * 1000;
        aStart = aBinarySearchStart(rows, 0, nrows - 1, target);
        
        if (aStart < nrows && rows[aStart].a != target)
            continue;
        
        aEnd = aBinarySearchEnd(rows, aStart, nrows - 1, target);
        bStart = bBinarySearchStart(rows, aStart, aEnd, 10);
        // b右侧是开口，所以依旧是找首元素位置
        bEnd = bBinarySearchStart(rows, bStart, aEnd, 50);
        
        for (j = bStart;j < bEnd;j++)
        {
            printf("%d,%d\n", rows[j].a, rows[j].b);
        }
    }
    
    return ;
}

// 任务3
/* 思路是使用二分法找到a分别为1000， 2000， 3000的首尾row
 * 然后在每对首尾之间对b寻找20->50的首尾，并将其记录到数组
 * 然后反复轮询数组，找到b的最小值进行输出
 * 寻找时间为O(log(N)), 输出时间为O(log(N))->O(N),空间复杂度O(1)
 * */
void
task3(const Row *rows, int nrows)
{
    int i, j, target, minB, minBidx, valid;
    int maxABase = 3;
    int aStart[maxABase], aEnd[maxABase], bStart[maxABase], bEnd[maxABase];
    
    for (i = 1;i <= maxABase;i++)
    {
        target = i * 1000;
        aStart[i-1] = aBinarySearchStart(rows, 0, nrows - 1, target);
        
        if (aStart[i-1] < nrows && rows[aStart[i-1]].a != target)
            continue;
        
        aEnd[i-1] = aBinarySearchEnd(rows, aStart[i-1], nrows - 1, target);
        bStart[i-1] = bBinarySearchStart(rows, aStart[i-1], aEnd[i-1], 10);
        // b右侧是开口，所以依旧是找首元素位置
        bEnd[i-1] = bBinarySearchStart(rows, bStart[i-1], aEnd[i-1], 50);
    }

    // 每轮输出a符合要求的b的最小值
    while (1)
    {
        minB = 50;
        valid = 0;
        
        for (i = 0;i < 3;i++)
        {
            if (bStart[i] < bEnd[i] && rows[bStart[i]].b < minB)
            {
                minB = rows[bStart[i]].b;
                minBidx = i;
                valid = 1;
            }
        }

        if (0 == valid)
            break;
        
        printf("%d,%d\n", rows[bStart[minBidx]].a, rows[bStart[minBidx]].b);
        bStart[minBidx]++;
    }
    
    return ;
}

// 任务4
目前任务3应该是优化过得，修改maxABase可以获得A取值的扩展性。